public class Offer_28 {
    /**
     * 剑指 Offer 28. 对称的二叉树
     * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
     * <p>
     * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
     * <p>
     * 1
     * / \
     * 2   2
     * / \ / \
     * 3  4 4  3
     * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
     * 1
     * / \
     * 2   2
     * \   \
     * 3    3
     */
    public boolean isSymmetric(TreeNode root) {
        //如果为null则为空
        if (root == null) {
            return true;
        }
        return symmetric(root.left, root.right);
    }

    private boolean symmetric(TreeNode left, TreeNode right) {
        //如果两个都为null，则对称返回true
        if (left == null && right == null) {
            return true;
        }
        // 如果是其中一个为null，那么则不对称
        if (left == null || right == null) {
            return false;
        }
        //值不对应返回false
        if (left.val != right.val) {
            return false;
        }
        return symmetric(left.right, right.left) && symmetric(left.left, right.right);
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(2);

        TreeNode treeNode4 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(4);

        TreeNode treeNode6 = new TreeNode(4);
        TreeNode treeNode7 = new TreeNode(3);

        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;

        Offer_28 offer = new Offer_28();
        System.out.println(offer.isSymmetric(treeNode1));
    }
}
